package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/14 9:30
 * @description：https://leetcode-cn.com/problems/course-schedule-iii/
 */
public class 课程表III {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    class Solution {
        public int scheduleCourse(int[][] courses) {
            Arrays.sort(courses, Comparator.comparingInt(o -> o[1]));
            PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
            int total = 0;
            for (int[] course : courses) {
                int ti = course[0], di = course[1];
                if (total + ti <= di) {
                    total += ti;
                    queue.offer(ti);
                } else if (!queue.isEmpty() && queue.peek() > ti) {
                    total -= queue.poll() - ti;
                    queue.offer(ti);
                }
            }
            return queue.size();
        }
    }
}
